package fun.ticsmyc.dataStructure;

import java.util.*;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.dataStructure
 * @date 2021-02-07 17:35
 */
public class LFU {

    /**
     * 使用LinkedHashSet  和 TreeMap
     */
    class LFUCache{

        /**
         * key -> node 映射
         */
        Map<Integer,Node> cache;
        /**
         * node的使用频率
         */
        TreeMap<Integer, LinkedHashSet<Node>> freqMap;

        int capacity;
        public LFUCache(int capacity) {
            this.capacity = capacity;
            cache = new HashMap<>();
            freqMap = new TreeMap<>();
        }

        public int get(int key) {
            if(!cache.containsKey(key)){
                return -1;
            }
            Node node = cache.get(key);
            //更新访问次数
            refreshFreq(node);
            return node.val;
        }

        public void put(int key, int value) {
            if(capacity==0) return;
            if(cache.containsKey(key)){
                Node node = cache.get(key);
                node.val=value;
                //更新访问次数
                refreshFreq(node);
            }else{
                if(cache.size() == capacity){
                    //删除频率最低的
                    LinkedHashSet<Node> nodes = freqMap.get(freqMap.keySet().iterator().next());
                    Node node = nodes.iterator().next();
                    cache.remove(node.key);
                    deleteNodeFromFreqMap(node);
                }
                Node node = new Node(key, value);
                cache.put(key,node);
                addNodeToFreqMap(node);
            }
        }

        private void refreshFreq(Node node) {
            deleteNodeFromFreqMap(node);
            node.freq++;
            addNodeToFreqMap(node);
        }

        public void addNodeToFreqMap(Node node){
            if(!freqMap.containsKey(node.freq)){
                freqMap.put(node.freq,new LinkedHashSet<>());
            }
            freqMap.get(node.freq).add(node);
        }
        public void deleteNodeFromFreqMap(Node node){
            LinkedHashSet<Node> nodes = freqMap.get(node.freq);
            nodes.remove(node);
            if(nodes.isEmpty()){
                freqMap.remove(node.freq);
            }
        }

        class Node{
            int key;
            int val;
            int freq;
            public Node(){}
            public Node(int k,int v){
                this.key=k;
                this.val =v;
                this.freq=1;
            }
        }
    }

    /**
     * 时间复杂度O（N）
     */
    class 使用优先队列实现的LFU {
        HashMap<Integer,Node> map ;
        PriorityQueue<Node> queue ;
        int size;
        int capacity;
        public 使用优先队列实现的LFU(int capacity) {
            map = new HashMap<>();
            queue =  new PriorityQueue<>((a,b)-> a.time ==b.time ?(a.no-b.no>0 ?1:0 ): a.time-b.time);
            this.capacity = capacity;
        }

        public int get(int key) {
            if(!map.containsKey(key)){
                return -1;
            }
            Node node = map.get(key);
            queue.remove(node);
            node.time++;
            node.no = System.nanoTime();
            queue.add(node);
            return node.val;
        }

        public void put(int key, int value) {
            if(capacity ==0) return;
            if(map.containsKey(key)){
                Node node =map.get(key);
                queue.remove(node);
                node.val = value;
                node.time++;
                node.no = System.nanoTime();
                queue.add(node);
            }else{
                if(size ==capacity){
                    Node del = queue.poll();
                    map.remove(del.key);
                    size--;
                }
                Node node =new Node(key,value);
                size++;
                queue.add(node);
                map.put(node.key,node);
            }
        }

        private class Node{
            int key;
            int val;
            int time;
            long no;
            public Node(int k,int v){
                this.no = System.nanoTime();
                this.key=k;
                this.val=v;
                this.time =1;
            }
        }

    }
}
